02. 강화학습 기초(1) - MDP와 벨만 방정식

• 강화학습이 결국 어떠한 방정식을 풀어내는 방법이라면 그 방정식이 무엇인지 아는 것이 중요할 것입니다
• 이 방정식은 벨만 방정식을 가리킵니다

MDP

• 구성 요소 : 상태 / 행동 / 보상 함수 / 상태 변환 확률 / 감가율
• 강화학습에서는 사용자가 문제를 정의해야 합니다

상태

• 상태 S는 에이전트가 관찰 가능한 상태의 집합
• 내가 정의하는 상태는 에이전트가 학습하기에 충분한 정보일까?란 생각을 곱씹어봐야함
• S = {(x1,y1), (x2,y2), (x3,y3), (x4,y4),(x5,y5)} 이런 식!

(위 사진은 참고를 위해 가져왔을 뿐, 설명과 상관 없음)

• 5 x 5 그리드월드에서 S = {(1,1),(1,2),(1,3)....(5,5)}
• 에이전트는 25개의 상태집합 안에 있는 상태를 탐험하게 됩니다. 시간은 t일 때 상태를 S_t로 표현합니다! 예를 들면 아래와 같음

$$ \begin{array}{c} S_t = (1,3) \end{array} $$

t= 1일때 S_t = (1,3)일 수도 있고, (4,2)일 수도 있음. 이것들은 확률 변수 ( Random Variable )라고 하며,

시간 t에서의 상태 S_t가 어떤 상태 s다를 수식으로 표현하면 아래와 같습니다

$$ \begin{array}{c} S_t = s \end{array} $$

행동

• 에이전트가 상태 S에서 할 수 있는 가능한 행동의 집합은 A입니다.
• 보통 에이전트가 할 수 있는 행동은 모든 상태에서 같습니다
• 시간 t에 에이전트가 특정한 행동 a를 했다면 아래와 같이 표현할 수 있습니다

$$ \begin{array}{c} A_t = a \end{array} $$

$$ \begin{array}{c} A_t \end{array} 는 어떤 t라는 시간에 집합 A에서 선택한 행동입니다. 이 친구도 확률변수 $$

A = {up, down, left, right}

보상 함수

• 에이전트가 학습할 수 있는 유일한 정보로 환경이 에이전트에게 주는 정보
• 보상함수 : 시간 t일 때 상태가 s이고 그 상태에서 행동 a를 했을 경우 받을 보상에 대한 기댓값 E
• 아래와 같은 수식으로 정의합니다
• 조건부 확률, 기댓값

$$ \begin{array}{c} R_s^a = E[R_t+1|S_t=s, A_t=a] \end{array} $$

• 어떤 상태에서 행동한 것은 시간 t인데, 보상을 받는 것은 t+1
• 보상을 에이전트가 알고 있는 것이 아니고 환경이 알려주기 때문에 위와같은 수식이 나온 것

상태 변환 확률

• 에이전트가 앞으로 나아가는 행동을 하면 s보다 앞에 있는 s'라는 상태에 도달할 것입니다
• 하지만 넘어진다거나 바람이 불면 상태가 변환할 수 있는데, 이를 수치적으로 표현한 것

$$ \begin{array}{c} P^a_{ss'} = P[S_t+1=s'|S_t=s, A_t=a] \end{array} $$

• 상태 변환 확률 : 상태 s에서 행동 a를 취했을 때 다른 상태 s'에 도달할 확률
• 에이전트가 알지 못하는 값으로서 에이전트가 아닌 환경의 일부이며, 환경의 모델이라고 부릅니다

감가율

• 에이전트는 항상 현재에 판단을 내리기 때문에 현재에 가까운 보상일수록 더 큰 가치를 가짐
• 현재로부터 일정 시간이 흐른 후, 보상을 받으면 100이라고 하지 않고 감가시켜 현재의 가치로 따짐

$$ \begin{array}{c} \gamma \in [0, 1] \end{array} $$

• 현재의 시간 t로부터 시간 k가 지난 후에 보상을 Rt+k를 받을 것이라면 아래와 같은 수식으로 표현 $$ \begin{array}{c} \gamma^{k-1}R{t+k} \end{array} $$

정책

• 정책은 모든 상태에서 에이전트가 할 행동
• 상태가 입력으로 들어오면 행동을 출력으로 내보내는 일종의 함수

$$ \begin{array}{c} \pi(a|s) = P[A_t=a|S_t=s] \end{array} $$

• 시간 t에 S_t = s에 에이전트가 있을 때 가능한 행동 중에서 A_t=a를 할 확률
• 최적 정책을 얻기 위해 현재의 정책보다 더 좋은 정책을 학습해나가는 것이 강화학습
• 환경은 에이전트에게 실제 보상과 상태를 알려줍니다. 이 과정에서 예상한 보상에 대해 틀렸다는 것을 알게 됩니다
• 이 때 받을 것이라 예상하는 보상을 가치함수라 합니다

가치함수

• MDP -> 가치함수 -> 행동 선택
• 현재 시간 t로부터 에이전트가 행동을 하면서 받을 보상들을 합한다면 아래와 같습니다 $$ \begin{array}{c} R_{t+1}+R_{t+2}+R_{t+3}+R_{t+4}+... \end{array} $$

• 에이전트가 시간마다 보상을 받을 수도 있고 게임이 끝날 때 한 번에 받을 수도 있습니다
• 감가율을 고려한 보상들의 합은(반환값) $$ \begin{array}{c} G_t = R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\gamma^3 R_{t+4}+... \end{array} $$

• 어떠한 상태에 있으면 앞으로 얼마의 보상을 받을 것인지에 대한 기댓값을 고려해볼 수 있는데, 이것이 바로 가치함수입니다 $$ \begin{array}{c} v(s) = E[G_t|S_t=s] \end{array} $$

• 각 스텝마다 받는 보상이 모두 확률적이고 반환값이 그 보상들의 합이므로 반환값은 확률변수입니다
• 하지만 가치함수는 확률변수가 아니라 특정 양을 나타내는 값으므로 소문자로 표현
• 상태의 가치를 고려하는 이유는 현재 에이전트가 갈 수 있는 상태들의 가치를 안다면 그 중에서 가장 가치가 높은 상태를 선택할 수 있기 때문

$$ \begin{array}{c} v(s) = E[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\gamma^3 R_{t+4}+...|S_t=s] \end{array} $$

이를 감마로 묶어주고 반환값의 형태로 표현하면

$$ \begin{array}{c} v(s) = E[R_{t+1}+\gamma G_{t+1}|S_t=s] \end{array} $$

이 보상은 앞으로 받을 것이라 예상하는 보상이기에 가치함수로 표현해보면

$$ \begin{array}{c} v_{\pi}(s) = E_{\pi}[R_{t+1}+\gamma v_{\pi}(S_{t_1})|S_t=s] \end{array} $$

큐함수 ( 행동 가치함수)

• 상태가 입력으로 들어오면 그 상태에서 앞으로 받을 보상의 합을 출력하는 함수
• 어떤 상태에서 어떤 행동이 얼마나 좋은지 알려주는 함수

$$ \begin{array}{c} q_{\pi}(s,a) \end{array} $$

• 가치함수와 큐함수 사이의 관계
  1. 각 행동을 했을 때 앞으로 받을 보상인 큐함수를 $$\begin{array}{c}\pi(a|s)\end{array}$$ 에 곱함
  2. 모든 행동에 대해 큐함수와 큐하수를 곱한 값을 더하면 가치함수가 됩니다

가치함수와 큐함수 사이의 관계식

$$ \begin{array}{c} v_{\pi}(s) = \Sigma\pi(a|s) * q_\pi(s,a) \end{array} $$

큐함수 또한 벨만 기대 방정식의 형태로 나타내면 아래와 같습니다

$$ \begin{array}{c} q_\pi(s,a) = E_{\pi}[R_{t+1}+\gamma q_{\pi}(S_{t+1}, A_{t+1})|S_t = s, A_t = a] \end{array} $$

벨만 기대 방정식 ( Bellman Expectation Equation )

• 정책을 고려한 가치함수의 표현 #### 현재 상태의 가치 함수와 다음 상태의 가치함수 사이의 관계를 말해주는 방정식

$$ \begin{array}{c} v_\pi(s) = E_\pi[R_{t+1}+\gamma v_\pi(S_{t_1})|S_t=s] \end{array} $$

벨만 기대 방정식 ( Bellman Expectation Equation )

• 가치 함수는 어떤 상태의 가치에 대한 기대를 나타냅니다. 어떤 상태의 가치함수는 에이전트가 그 상태로 갈 경우에 앞으로 받을 보상의 합에 대한 기댓값

$$ \begin{array}{c} v_\pi(s) = \Sigma\pi(a|s)(R_{t+1}+\gamma\Sigma P_{ss'}^a v_{\pi}(s')) \end{array} $$

위 식을 이렇게 표현할 수 있습니다

• 각 행동에 대해 그 행동을 할 확률을 고려하고
• 각 행동을 했을 때 받을 보상과
• 다음 상태의 가치 함수를 고려합니다

• 참 가치함수 : 어떤 정책을 따라서 움직였을 경우에 받게 되는 보상에 대한 참값

• 최적의 가치 함수 : 수많은 정책 중에서 가장 높은 보상을 주는 가치함수

• 더 좋은 정책이라는 것은 가치함수(수(정책을 따라갔을 때 받을 보상들의 합)를 통해 판단할 수 있습니다

• 최적의 가치함수는 아래와 같이 표현합니다

$$ \begin{array}{c} v_*(s) = max[v_{\pi}(s)] \end{array} $$

최적의 큐함수 $$ \begin{array}{c} q_*(s,a) = max[q_{\pi}(s,a)] \end{array} $$

선택 상황에서 판단 기준은 큐함수!

$$ \begin{array}{c} \pi_*(s,a) = > 1 if a = argmax q_{*}(s,a) /// 0 otherwise \end{array} $$

큐함수 중에서 max를 취하는 것이 최적의 가치함수.

$$ \begin{array}{c} v_*(s) = max[q_*(s,a)|S_t=s, A_t=a] \end{array} $$

그렇다면 이제 큐함수를 가치함수로 고쳐서 표현하면!!!! 벨만 최적 방정식이 탄생!!!!!!!!!!

$$ \begin{array}{c} v_*(s) = max E[R_{t+1}+\gamma v_*(S_{t+1})|S_t = s, A_t = a] \end{array} $$